#include <cstdio>
#include <iostream>
#include <type_traits>
#include <vector>
using namespace std;

int max_cost(const vector<int> &W, const vector<int> &C, int m, int n)
{
	if (n == 0 || m == 0) {
		return 0;
	}

	int maxc = max_cost(W, C, m, n - 1);
	if (W[n] <= m) {
		maxc = max(maxc, max_cost(W, C, m - W[n], n) + C[n]);
	}
	return maxc;
}

int max_cost(const vector<int> &W, const vector<int> &C, int m, int n, vector<vector<int>> &rd)
{
	if (rd[n][m] != -1) {
		return rd[n][m];
	}

	if (n == 0 || m == 0) {
		return rd[n][m] = 0;
	}

	int maxc = max_cost(W, C, m, n - 1, rd);
	if (W[n] <= m) {
		maxc = max(maxc, max_cost(W, C, m - W[n], n, rd) + C[n]);
	}
	return rd[n][m] = maxc;
}

using vec = vector<int>;
using vec_2d = vector<vector<int>>;

int max_cost_dp(const vec &W, const vec &C, int m, int n)
{
	vec_2d dp(n + 1, vec(m + 1, 0));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = dp[i - 1][j];
			if (W[i] <= j) {
				dp[i][j] = max(dp[i][j], dp[i][j - W[i]] + C[i]);
			}
		}
	}
	return dp.back().back();
}

int max_cost_dps(const vec &W, const vec &C, int m, int n)
{
	vec dp(m + 1, 0);
	for (int i = 0; i <= n; i++) {
		for (int j = W[i]; j <= m; j++) {
			dp[j] = max(dp[j], dp[j - W[i]] + C[i]);
		}
	}
	return dp.back();
}

int main()
{
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	int M, N;
	cin >> M >> N;

	vector<int> weight(N + 1, 0);
	vector<int> cost(N + 1, 0);
	vector<vector<int>> rd(N + 1, vector<int>(M + 1, -1));
	for (int i = 1; i <= N; i++) {
		cin >> weight[i] >> cost[i];
	}

	cout << "max=" << max_cost_dps(weight, cost, M, N) << endl;
	return 0;
}